import java.sql.Array;

/**
 * 27. 移除元素
 * <p>
 * 给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
 * 不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
 * 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
 */
public class removeElement {
    public static void main(String[] args) {
        int number = 1000;


        long time = 0;
        long memory = 0;
        for (int i = 0; i < number; i++) {
            Runtime r = Runtime.getRuntime();
            r.gc();//计算内存前先垃圾回收一次
            long start = System.currentTimeMillis();//开始Time
            long startMem = r.totalMemory(); // 开始Memory


            int[] nums1 = {3, 2, 2, 3};
            int[] nums2 = {0, 1, 2, 2, 3, 0, 4, 2};
            int[] nums3 = {0, 1, 2, 2, 3, 0, 4, 2};
            int[] nums4 = {3, 2, 2, 3};
            int[] nums5 = {0, 1, 2, 2, 3, 3, 4, 2, 1};
            removeElement_3(nums1, 3);
            removeElement_3(nums2, 2);
            removeElement_3(nums3, 0);
            removeElement_3(nums4, 2);
            removeElement_3(nums5, 3);


            long endMem = r.freeMemory(); // 末尾Memory
            long end = System.currentTimeMillis();//末尾Time
            //输出
            time += end - start;
            memory += ((startMem - endMem) / 1024);
            //            System.out.println("用时消耗: " + String.valueOf(end - start) + "ms");
            //            System.out.println("内存消耗: " + String.valueOf((startMem - endMem) / 1024) + "KB");
        }

        System.out.println(time + "ms  " + memory + "KB  " + (time / number) + "ms  " + (memory / number) + "KB");
        //        System.out.println("用时消耗: " + time + "ms");
        //        System.out.println("内存消耗: " + memory + "KB");
        //        System.out.println("平均用时消耗: " + (time / number) + "ms");
        //        System.out.println("平均内存消耗: " + (memory / number) + "KB");
    }

    /**
     * 看了题解，把int n删除了。结果内存占用更高。
     * <p>
     * 0 ms 40.1 MB
     */
    public static int removeElement_1(int[] nums, int val) {
        int left = 0;
        for (int right = 0; right < nums.length; right++) {
            if (nums[right] != val) {
                nums[left] = nums[right];
                left++;
            }
        }
        return left;
    }

    /**
     * 区别不大啊？
     * 39.9 MB
     *
     * @param nums
     * @param val
     * @return
     */
    public static int removeElement_2(int[] nums, int val) {
        int n = nums.length;
        int left = 0;
        for (int i = 0; i < n; i++) {
            if (nums[i] != val) {
                nums[left] = nums[i];
                left++;
            }
        }
        return left;
    }

    public static int removeElement_3(int[] nums, int val) {
        int left = 0;
        for (int item : nums) {
            if (item != val) {
                nums[left] = item;
                left++;
            }
        }
        return left;
    }
}


